In a harsh radio environment, where deep fading and noisy conditions are commonplace, the availability of a link between any two nodes is uncertain. One can expect that loss of connectivity may last for an extended period of time. Yet, a team of ad-hoc mobile nodes moving around the harsh environment need to send data to all the other radio nodes in the environment. Due to the uncertainty of the availability of links, a large percent of the sent data do not arrive at all the other nodes when first transmitted. Accordingly, these data must subsequently be sent again.
Existing methods, such as epidemic algorithms and gossip algorithms, are traditionally used to retransmit data that had not initially been received at all of the nodes. In these approaches, each node randomly picks a neighbor, finds out what data is missing from that neighbor and transmits the missing data. However, retransmissions using these methods are inefficient because, among other things, redundant data is transmitted.
In “Epidemic Algorithms for Replicated Database Management” in ACM Symposium on Principles of Distributed Computing, 1987, Demers et al. describe anti-entropy and rumor mongering as examples of epidemic processes. In anti-entropy, each site regularly chooses another site at random and exchanges information with it. This is a reliable technique for propagating data, but is quite cumbersome, because the exchanges can involve redundant or repetitious data transmission. In rumor mongering, a site receives an update, or “hot rumor” which it tries to share with other sites by asking one of those other sites whether it has the hot rumor. If the hot rumor is shared with one site, another site can be asked. Rumor mongering again can involve redundant transmission of data, and also is not as reliable as anti-entropy because there is a chance that an update will not reach all sites.
R. Chandra, et al., in “Anonymous Gossip: Improving Multicast Reliability in Mobile Ad-Hoc Networks,” International Conference on Distributed Computing Systems, 2001, describe implementing periodic anonymous gossip in the background to ensure that most of the reachable members of a network receive packets which have been multicast to the group. In a round of gossip, an originator node randomly selects another node in its group and sends the selected node information about the originator's messages. If the selected node does not already have the originator's messages, the two nodes can exchange messages. However, transmission of duplicate or redundant data can occur.
Among the problems of the aforementioned approaches is the use of a point-to-point or node-to-node solution as well as the lack of information regarding what the rest of the nodes are doing. As a result, these approaches are not optimized for the radio environment, which is inherently a broadcast medium, transmitting to multiple nodes simultaneously.